// 排列组合
#include <stdio.h>

/// @brief 列出从length个数中抽取r个数的所有组合方式（无序）
/// @param arr 存放全部的数
/// @param length arr的长度
/// @param r 一个组合的元素个数
/// @param temp 递归变量：存放每次选取组合时选取的元素的下标
/// @param remain 递归变量：表示这次组合选择后还需要选择几个元素
void combine(int arr[], int length, int r, int temp[], int remain)
{
	// 一次组合完成结束递归
	if (remain == 0)
	{
		int i;
		for (i = 0; i < r; i++)
		{
			printf("%d", arr[temp[i]]);
		}
		printf("\n");
		return;
	}
	// 否则进行递归选择
	int j;
	for (j = length; j >= remain; j--)
	{
		// 先从数组末尾选择一个并暂存入此次选择的结果
		temp[remain - 1] = j - 1;
		// 然后以0到最后一个之前的范围内进行递归选择，已经选择了一个因此下一步只需选择remian - 1个
		combine(arr, j - 1, r, temp, remain - 1);
	}
}

/// @brief 列出一个数列的全部子集（无序）
/// @param arr 数列
/// @param length 数列长度
void allSubCollection(int arr[], int length)
{
	int i, temp[length];
	for (i = 0; i <= length; i++)
	{
		combine(arr, length, i, temp, i);
	}
}

/// @brief 交换两个元素
/// @param a 交换第一个元素的指针
/// @param b 交换第二个元素的指针
void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

/// @brief 输出数组全排列
/// @param arr 数组
/// @param start 开始排列的索引
/// @param end 结束排列的索引
void allRange(int arr[], int start, int end)
{
	int i;
	if (start == end)
	{
		for (i = 0; i <= end; i++)
		{
			printf("%d", arr[i]);
		}
		printf("\n");
		return;
	}
	for (i = start; i <= end; i++)
	{
		swap(&arr[i], &arr[start]);
		allRange(arr, start + 1, end);
		swap(&arr[i], &arr[start]);
	}
}

int main()
{
	int a[] = {1, 2, 3, 4, 5, 6};
	allRange(a, 0, 2);
	return 0;
}